#include <assert.h>
#include <iostream>
using namespace std;

template <class T>
struct list_node{ //使用struct公开成员变量，方便Mylist直接进行访问。
  T _data;
  list_node *_next;
  list_node *_prev;
  
  list_node(const T &val = T())
    :_data(val),
    _next(nullptr),
    _prev(nullptr)
  {}
  
  list_node(T &&val = T())
    :_data(forward<T>(val)),
    _next(nullptr),
    _prev(nullptr)
  {}
};

//list_iterator的成员变量只有一个指向节点的指针。
//但其中封装了list迭代器的方法：
//1.解引用返回数据_data引用
//2.箭头返回数据_data的地址
//3.++操作实现了链表指针的移动
template <class T, class Ref, class Ptr>
struct list_iterator{
  typedef list_node<T> Node;
  typedef list_iterator<T, Ref, Ptr> iterator;
  Node *_pnode;

  list_iterator(Node *pnode)
    :_pnode(pnode)
  {}

  //list_iterator的拷贝构造，析构，赋值重载使用默认生成的即可。
    
//*和->操作涉及普通对象和const对象的权限问题，需要传入Ref和Ptr泛型返回值，
//普通对象传普通引用和普通指针；const对象传const引用和const指针。
//这里还要区分const list对象和const iterator对象。
  Ref operator*() const{
    return _pnode->_data;
  }

  Ptr operator->() const{
    return &(_pnode->_data);
  }

  iterator& operator++(){
    _pnode = _pnode->_next;
    return *this;
  }

  iterator operator++(int){
    iterator tmp(*this);
    _pnode = _pnode->_next;
    return tmp;
  }

  iterator& operator--(){
    _pnode = _pnode->_prev;
    return *this;
  }

  iterator operator--(int){
    iterator tmp(*this);
    _pnode = _pnode->_prev;
    return tmp;
  }
  
  bool operator!=(const iterator &it) const{
    return _pnode!=it._pnode;
  }

  bool operator==(const iterator &it) const{
    return _pnode==it._pnode;
  }
};

template <class T>
class Mylist{
  typedef list_node<T> Node;
  Node *_phead;

  public:
  //iterator
  typedef list_iterator<T, T&, T*> iterator;
  typedef list_iterator<T, const T&, const T*> const_iterator;

  iterator begin(){
    return iterator(_phead->_next);
  }

  iterator end(){
    return iterator(_phead);
  }

  const_iterator begin() const{
    return const_iterator(_phead->_next);
  }

  const_iterator end() const{
    return const_iterator(_phead);
  }
  
  //constructor & destructor
  void empty_initialize(){
    _phead = new Node(T());
    _phead->_next = _phead;
    _phead->_prev = _phead;
  }

  Mylist(){
    empty_initialize();  
  }

  template <typename InputIterator>
    Mylist(InputIterator first, InputIterator last){
      empty_initialize(); //交换前必须要进行空初始化，否则会访问野指针崩溃
      while(first!=last)
      {
        push_back(*first);
        ++first;
      }
    }

  void swap(Mylist &mlt){
    std::swap(_phead, mlt._phead);
  }

  Mylist(const Mylist &mlt){
    empty_initialize(); //交换前必须要进行空初始化，否则会访问野指针崩溃
    Mylist tmp(mlt.begin(), mlt.end());
    swap(tmp);
  }

  Mylist& operator=(Mylist mlt){
    swap(mlt);
    return *this;
  }

  void clear(){
   iterator it = begin();
   while(it != end())
   {
     it = erase(it);
   }
  }

  ~Mylist(){
    clear(); //清除所有数据节点
    delete _phead; //释放哨兵位节点
  }

  iterator insert(iterator pos, const T &val){
    Node *cur = pos._pnode;
    Node *prev = cur->_prev;
    Node *newnode = new Node(val);
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    return iterator(newnode);
  }

  iterator insert(iterator pos, T &&val){
    Node *cur = pos._pnode;
    Node *prev = cur->_prev;
    Node *newnode = new Node(forward<T>(val));
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    return iterator(newnode);
  }

  void push_back(const T &val){
    insert(end(), val);
  }

  void push_back(T &&val){
    //insert(end(), val);
    insert(end(), forward<T>(val));
  }

  void push_front(const T &val){
    insert(begin(), val);
  }

  iterator erase(iterator pos){
    assert(pos != end());
    Node *cur = pos._pnode;
    Node *prev = cur->_prev;
    Node *next = cur->_next;
    next->_prev = prev;
    prev->_next = next;
    delete cur;
    return iterator(next);
  }

  void pop_back(){
    assert(_phead->_next != _phead);
    erase(--end());
  }

  void pop_front(){
    assert(_phead->_next != _phead);
    erase(begin());
  }
};
